1. Technical Field
The present invention relates generally to data processing systems. More particularly the present invention relates to protecting data processing systems. Still more particularly, the present invention relates to constructing firewalls that protect data processing systems.
2. Description of the Related Art
In the past, so-called “hackers” have accessed and compromised private networks through direct dialing of modems coupled to the private network. With the advent of the Internet, individuals, business, and government have discovered that communication between networks could be established via the Internet instead of relying on connections between private networks. However, connecting a private network to the Internet introduces significant security problems for the data stored on a private network.
When a private network is coupled to the Internet, hackers may utilize the Internet as a means of accessing the private network. Therefore, many businesses, individuals, and the government utilize protective software and/or hardware known as a “firewall” to protect the private network from unauthorized access. A firewall is typically a hardware and/or software module that provides secure access to and from the private network by examining any packet of data that attempts to enter or leave the private network at some entry point. Depending on the configuration of an individual packet, the firewall determines whether the packet should proceed on its way or be discarded. To perform this function, the firewall includes a sequence of rules, which are in the form <predicate>→<decision>, where <predicate> is a Boolean expression over the different fields of a packet, and the <decision> of this rule is an operation applied to the packet.
Those with skill in this art will appreciate that the design of a firewall involves the design of a sequence of rules, which is not an easy task. Often, designers modify existing firewalls by adding more rules to cover cases that were not anticipated in the original design. As more threats to a private network materialize, the firewall must be fortified with more rules. The increasing number of rules requires more processing for each packet that passes through the firewall. In the prior art, most research in the area of firewalls have been dedicated to developing efficient data structures that can decrease the time required to process each packet through the firewall rules. Examples of such data structures are tree data structures, area-based quadtrees, and fat inverted segment trees.